11387. Игра в карточки

Хусейн с Ярославом играют в карточки. На столе в ряд лежат n карточек, на которых написаны различные числа. Игроки ходят по очереди. Первым ходит Хусейн. За один ход игрок может взять или крайнюю слева карточку, или крайнюю справа. Игрок всегда выбирает карточку с большим числом. Игра заканчивается, когда на столе не останется карточек. Найдите сумму чисел на карточках Хусейна и Ярослава к концу игры.

Вход. Первая строка содержит количество карточек n (1 ≤ n ≤ 10000) на столе. Вторая строка содержит n натуральных чисел, записанных на карточках. Все числа не превышают 10⁹.

Выход. Выведите сумму чисел на карточках, которые собрали Хусейн и Ярослав к концу игры.

Пример входа	Пример выхода
7 4 7 5 1 12 8 2	18 21

РЕШЕНИЕ

два указателя

Анализ алгоритма

Пусть массив m содержит числа, записанные на карточках. Инициализируем указатели i = 0 на начало массива и j = n – 1 на конец массива. 

На каждом ходу игрок берет карточку с максимальным значением max (m[i], m[j]), после чего карточка убирается со стола (совершаем операцию i++ если выбрана карточка m[i] и j-- если выбрана карточка m[j]). Для каждого из игроков подсчитываем сумму выбранных карточек в двух переменных. Процесс продолжается до тех пор, пока все карточки не будут убраны со стола, то есть, пока указатели i и j не сойдутся.

Пример

Игра будет проходить следующим образом.

Реализация алгоритма

Объявим рабочие массивы. Сумму чисел на карточках Хусейна и Ярослава будем подсчитывать соответственно в res[0] и res[1].

int m[10001], res[2];

Читаем входные данные.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

Установим указатели i = 0 и j = n – 1.

i = 0; j = n - 1;

Игроки последовательно совершают n ходов. Ходы для четного k совершает Хусейн, а ходы для нечетного k совершает Ярослав. Соответственно, сумма Хусейна будет накапливаться в res[0], а сумма Ярослава – в res[1].

for (k = 0; k < n; k++)

{

На каждом ходу игрок выбирает карточку с максимальным значением max(m[i], m[j]).

if (m[i] > m[j])

res[k % 2] += m[i++];

else

res[k % 2] += m[j--]; ;

}

Выводим ответ.

printf("%d %d\n", res[0], res[1]);

Python рализация

Читаем входные данные.

n = int(input())

m = list(map(int, input().split()))

Установим указатели i = 0 и j = n – 1.

i, j = 0, n – 1

Сумму чисел на карточках Хусейна и Ярослава будем подсчитывать соответственно в res[0] и res[1].

res = [0, 0]

Игроки последовательно совершают n ходов. Ходы для четного k совершает Хусейн, а ходы для нечетного k совершает Ярослав. Соответственно, сумма Хусейна будет накапливаться в res[0], а сумма Ярослава – в res[1].

for k in range(n):

На каждом ходу игрок выбирает карточку с максимальным значением max(m[i], m[j]).

if m[i] > m[j]:

res[k % 2] += m[i]

i += 1

else:

res[k % 2] += m[j]

j -= 1

Выводим ответ.

print(res[0], res[1])